package puf.m2.automaton.converter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

import puf.m2.automaton.AbstractFiniteAutomaton;
import puf.m2.automaton.Automaton;
import puf.m2.automaton.State;
import puf.m2.automaton.Transition;
import puf.m2.automaton.Word;

/**
 * Provides tools to convert a two-way non-deterministic automaton to
 * a two-way deterministic automaton.
 */
public class NFAToDFAConverter {
    /** The NFA we're converting to a DFA. */
    private Automaton nfa;

    /** The DFA being built. */
    private Automaton dfa;

    /** The final answer DFA, used for reference. */
    private Automaton answer;

    public NFAToDFAConverter(Automaton nfa) {
        dfa = new AbstractFiniteAutomaton();
        this.nfa = nfa;
        answer = convertToDFA(nfa);
    }

    /**
     * Returns the initial state for <CODE>dfa</CODE>. A state is created to
     * represent the initial state from <CODE>nfa</CODE> (and its closure),
     * and added to <CODE>dfa</CODE>. The initial state of <CODE>dfa</CODE>
     * is set to the returned state.
     *
     * @param nfa
     *            the nfa being converted to a dfa
     * @param dfa
     *            the dfa being built during the conversion.
     */
    public State createInitialState(Automaton nfa, Automaton dfa) {
        /** get closure of initial state from nfa. */
        State initialState = nfa.getInitialState();
        State[] initialClosure = getClosure(initialState, nfa);
        /** create state in dfa to represent closure of initial state in nfa. */
        State state = createStateWithStates(dfa, initialClosure, nfa);
        /** set to initial state in dfa. */
        dfa.setInitialState(state);
        return state;
    }

    /**
     * Creates a state in <CODE>dfa</CODE>, labelled with the set of states
     * in <CODE>states</CODE>, which are all states from <CODE>nfa</CODE>.
     *
     * @param dfa
     *            the dfa. the automaton the state is added to
     * @param states
     *            the set of states from the nfa that this created state in the
     *            dfa will represent
     * @param nfa
     *            the nfa
     * @return the created state
     */
    public State createStateWithStates(Automaton dfa, State[] states,
            Automaton nfa) {
        State state = dfa.createState();
        if (hasFinalState(states, nfa)) {
            dfa.addFinalState(state);
        }
        return state;
    }

    /**
     * Returns true if one or more of the states in <CODE>states</CODE> are
     * final.
     * @param states
     *            the set of states
     * @param automaton
     *            the automaton that contains <CODE>states</CODE>
     * @return true if one or more of the states in <CODE>states</CODE> are
     *         final
     */
    public boolean hasFinalState(State[] states, Automaton automaton) {
        for (int k = 0; k < states.length; k++) {
            if (automaton.isFinalState(states[k]))
                return true;
        }
        return false;
    }

    /**
     * Returns the closure of <CODE>state</CODE>, that is, all states
     * reachable from <CODE>state</CODE> without changing any internal state
     * (e.g. stack, tape, input) via lambda transitions.
     *
     * @param state
     *            the state whose closure is being taken.
     * @param automaton
     *            the automaton
     * @return the set of states that represent the closure of state.
     */
    public static State[] getClosure(State state, Automaton automaton) {
        List<State> list = new ArrayList<State>();
        list.add(state);
        for (int i = 0; i < list.size(); i++) {
            state = (State) list.get(i);
            Transition transitions[] = automaton.getTransitionsFromState(state);
            for (int k = 0; k < transitions.length; k++) {
                Transition transition = transitions[k];
                EpsilonTransitionChecker checker = EpsilonTransitionChecker.getChecker();
                /** if epsilon transition */
                if (checker.isEpsilonTransition(transition)) {
                    State toState = transition.target();
                    if (!list.contains(toState)) {
                        list.add(toState);
                    }
                }
            }
        }
        return (State[]) list.toArray(new State[0]);
    }

    /**
     * Returns a deterministic finite state automaton equivalent to <CODE>automaton</CODE>.
     * <CODE>automaton</CODE> is not at all affected by this conversion.
     *
     * @param automaton
     *            the automaton to convert to a dfa.
     * @return a deterministic finite state automaton equivalent to <CODE>automaton</CODE>.
     */
    public Automaton convertToDFA(Automaton automaton) {
        /** check if actually nfa. */
        AutomatonChecker ac = AutomatonChecker.getChecker();
        if (!ac.isNFA(automaton)) {
            return (Automaton) automaton.clone();
        }
        /** remove multiple character labels. */
        if (hasMultipleCharacterLabels(automaton)) {
            removeMultipleCharacterLabelsFromAutomaton(automaton);
        }
        /** create new finite state automaton. */
        Automaton dfa = new AbstractFiniteAutomaton();
        State initialState = createInitialState(automaton, dfa);
        /**
         * get initial state and add to list of states that need to be expanded.
         */
        ArrayList list = new ArrayList();
        list.add(initialState);
        /** while still more states to be expanded. */
        while (!list.isEmpty()) {
            ArrayList statesToExpand = new ArrayList();
            Iterator it = list.iterator();
            while (it.hasNext()) {
                State state = (State) it.next();
                /** expand state. */
                statesToExpand.addAll(expandState(state, automaton, dfa));
                it.remove();
            }
            list.addAll(statesToExpand);
        }

        return dfa;
    }

    private void removeMultipleCharacterLabelsFromAutomaton(Automaton automaton) {

    }

    private boolean hasMultipleCharacterLabels(Automaton automaton) {
        return false;
    }

    private Collection expandState(State state, Automaton automaton,
            Automaton dfa2) {
        return null;
    }
}
